
import com.sun.xml.internal.ws.addressing.WsaActionUtil;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: lishuo
 * Date: 2023-03-19
 * Time: 19:07
 */

public class Test {
    //-------------------------------------------Day01-----------------------------------------------
    //NO.1
    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            int n = scanner.nextInt();
            int[] array = new int[3 * n];
            for (int i = 0; i < 3 * n; i++) {
                int ret = scanner.nextInt();
                array[i] = ret;
            }
            Arrays.sort(array);
            long max = 0;//在这里掉坑了
            for (int i = n; i < 3 * n; i += 2) {
                max += array[i];
            }
            System.out.println(max);
        }
    }

    //NO.2
    public static void main2(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s1 = scanner.nextLine();
        String s2 = scanner.nextLine();
        ArrayList<Character> list = new ArrayList<>();
        for (int i = 0; i < s1.length(); i++) {
            char ch = s1.charAt(i);
            //ch+"";
            if (!s2.contains(String.valueOf(ch))) {
                list.add(ch);
            }
        }

        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i));
        }
    }

    //NO.3
    // 访问权限不能比父类中被重写的方法的访问权限更低。例如：如果父类方法被public修饰，则子类中重写该方法就不能声明为 protected.

    //-------------------------------------------Day02-----------------------------------------------
    //NO.1 Java抽象知识点

    //NO.2倒置字符串
    public static void rev(StringBuilder str, int s1, int s2) {
        while (s1 <= s2) {
            char tmp = str.charAt(s1);
            str.setCharAt(s1, str.charAt(s2));
            str.setCharAt(s2, tmp);
            s1++;
            s2--;
        }
    }

    public static void main3(String[] args) {
        Scanner scanner = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        String str = scanner.nextLine();
        sb.append(str);
        sb.reverse();
        System.out.println(sb);


        int s1 = 0;
        int s2 = 0;
        for (int i = 1; i < str.length(); i++) {
            if (sb.charAt(i) == ' ') {
                s2 = i - 1;
                rev(sb, s1, s2);
                s1 = i + 1;
            }
        }
        //掉到这里了
        s2 = sb.length() - 1;
        rev(sb, s1, s2);
        System.out.println(sb);
    }


    // 方法二
    public static void reverse(char[] arr, int start, int end) {
        while (start < end) {
            char tmp = arr[start];
            arr[start] = arr[end];
            arr[end] = tmp;
            start++;
            end--;
        }
    }

    public static void main4(String args[]) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        char[] arr = str.toCharArray();
        int len = arr.length;
        reverse(arr, 0, len - 1);
        int start = 0;
        while (start < len) {
            int end = start;
            while (end < len && arr[end] != ' ') {
                end++;
            }
            reverse(arr, start, end - 1);
            start = end + 1;
        }
        String ansEnd = new String(arr);
        System.out.println(ansEnd);
    }


    //No.3最小排序子序列
    public static void main5(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] array = new int[n + 1];
        for (int i = 0; i < n; i++) {
            array[i] = scanner.nextInt();
        }
        int i = 0;
        int count = 0;
        while (i < n) {
            // 下面是三种情况：
            if (array[i] < array[i + 1]) {
                while (i < n && array[i] < array[i + 1]) {
                    i++;
                }
                count++;
                i++;
            } else if (array[i] == array[i + 1]) {
                i++;
            } else {
                while (i < n && array[i] > array[i + 1]) {
                    i++;
                }
                count++;
                i++;
            }
        }
        System.out.println(count);
    }

    //-------------------------------------------Day03-----------------------------------------------
    public static boolean isDigit(char x) {
        if (x >= '0' && x <= '9') {
            return true;
        }
        return false;
    }

    public static void main6(String[] args) {
        // 输入
        Scanner scanner = new Scanner(System.in);
        String src = scanner.nextLine();
        int count = 0;
        int i = 0;
        int start = 0;
        while (i < src.length()) {
            //统计一趟数字字符个数
            int tmp = 0;
            if (isDigit(src.charAt(i))) {
                while (i < src.length() && isDigit(src.charAt(i))) {
                    //统计这一趟数字字符个数
                    tmp++;
                    i++;
                }
            }
            if (tmp > count) {
                //记录数字字符起始位置
                start = i - tmp;
                //如果比现有最长字符长，就更新长度
                count = tmp;
            }
            i++;
        }
        for (int j = start; j < start + count; j++) {
            System.out.print(src.charAt(j));
        }

    }

    // 方案一：暴力求解，数组排序找中值(1 1 1 2 2 2 2 3 3 3 3 3)不靠谱
    public static void main7(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 创建数组
        int n = scanner.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = scanner.nextInt();
        }
        // 数组排序
        Arrays.sort(array);
        // 找中间值
        System.out.println(array[array.length / 2]);

    }

    // 方案二：摩尔根投票法，靠谱
    public int MoreThanHalfNum_Solution(int[] numbers) {
        int i = 0;
        int len = numbers.length;
        //统计票数
        int count = 0;
        //设置初始比对值
        int tmp = numbers[0];
        while (i < len) {
            if (numbers[i] == tmp) {
                count++;
            } else {
                count--;
            }
            if (count == 0) {
                //注意这里一定是i+1
                tmp = numbers[i + 1];
            }
            i++;
        }
        return tmp;
    }

    //-------------------------------------------Day04-----------------------------------------------
    //No1.
    public static void main8(String[] args) {
        //小数不精确问题？？？
        //思路：先解方程组A-B和A+B,然后再带入B-C和B+C验证
        //输入数据
        Scanner scanner = new Scanner(System.in);
        double[] array = new double[4];
        for (int i = 0; i < array.length; i++) {
            array[i] = scanner.nextInt();
        }
        //求解方程A-B和A+B
        double A = (array[0] + array[2]) / 2.0;
        double B = array[2] - A;
        //A、B为小数时，A、B小于0时
        if (A != (int) A || B != (int) B || A < 0 || B < 0) {
            System.out.println("No");
            return;
        }
        //解方程B-C和B+C并验证
        double C1 = B - array[1];
        double C2 = array[3] - B;
        //两个C不同时、C为小数时、C小于0时
        if (C1 != C2 || C1 != (int) C1 || C1 < 0) {
            System.out.println("No");
            return;
        }
        System.out.println((int) A + " " + (int) B + " " + (int) C1);
    }

    //No2.
    // 方案一：使用栈(错误点1：开始没有考虑负数；错误点2：没有考虑M=0的情况)
    public static void main9(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int M = scanner.nextInt();
        if (M == 0) {
            System.out.print(0);
            return;
        }
        int N = scanner.nextInt();
        char[] array = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};
        Stack<Character> stack = new Stack<>();
        int tmp = M;
        if (tmp < 0) {
            tmp *= -1;
        }
        while (tmp != 0) {
            stack.push(array[tmp % N]);
            tmp = tmp / N;
        }
        if (M < 0) {
            stack.push('-');
        }
        while (!stack.isEmpty()) {
            System.out.print(stack.pop());
        }
    }
    //-------------------------------------------Day05-----------------------------------------------

    //No.1
    public static void main10(String[] args) {
        //输入
        Scanner scanner = new Scanner(System.in);
        String A = scanner.nextLine();
        String B = scanner.nextLine();
        int count = 0;
        //创建列表并初始化
        List<Character> list = new LinkedList<>();
        for (int i = 0; i < A.length(); i++) {
            list.add(A.charAt(i));
        }
        List<Character> list2 = new LinkedList<>();
        for (int i = 0; i < B.length(); i++) {
            list2.add(B.charAt(i));
        }
        //在不同位置插入并分别判断
        //第二个错误：<=不是<
        for (int i = 0; i <= A.length(); i++) {
            //指定位置插入

            list.addAll(i, list2);
            //判断
            int start = 0;
            //第三错误：需要-1
            int end = A.length() + B.length() - 1;
            while (start < end) {
                if (!list.get(start).equals(list.get(end))) {
                    break;
                }
                start++;
                end--;
            }
            if (start >= end) {
                count++;
            }

            //第一个错误：list删除机制混淆
            int n = i;
            while (n < B.length() + i) {
                list.remove(i);
                n++;
            }
        }
        System.out.println(count);
    }


    //NO2.不会。呜呜呜
    public static void main11(String[] args) {
        //输入数据并构造数组
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = scanner.nextInt();
        }
        if (n == 1) {
            System.out.println(array[0]);
        }
        //
        int max = array[0];
        int i = 1;
        //找到大于0的max
        if (max < 0) {
            while (i < array.length && array[i] < 0) {
                max = max > array[i] ? max : array[i];
                i++;
            }
        }
        while (i < array.length) {
            int tmp = 0;
            while (i < array.length && array[i] >= 0) {
                tmp += array[i];
                i++;
            }
            while (i < array.length && array[i] < 0) {
                i++;
            }
            if (tmp > max) {
                max = tmp;
            }
        }
        System.out.println(max);
    }

    //-------------------------------------------Day06-----------------------------------------------
    //No.1
    // float f = -412.0f;//需要加f或F
    // abstract 和 final不能同时存在

    //No.2:历时两天终于解决！！！
    public static void main12(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int M = scanner.nextInt();
        int N = scanner.nextInt();

        //关键点：任意八个格子都有4个有效值？
        //4 5 = 20 = 16 + 4-->4*x=4
        //7 2 = 14 = 8 + 6-->2*x=6
        int total = M * N;
        //有几个8就有几个4
        int count = (total / 8) * 4;
        //余数单独判断，由于方阵具有规律，这里只需要在第一个方阵判断即可
        int other = total % 8;
        int min = M < N ? M : N;
        switch (other) {
            case 1:
                //余数为1只可能是 1*1，9*1，17*1……
                count += 1;
                break;
            case 2:
                //余数为2 只可能是 2*1,10*1……
                count += 2;
                break;
            case 3:
                //余数为3 只可能是 3*1,11*1
                count += 2;
                break;
            case 4:
                // 余数为4比较特殊
                // 当较小值为偶数时，对照方阵1可知，有效值为4
                if (min % 2 == 0) {
                    count += 4;
                } else {
                    // 当较小值为奇数时，对照方阵1可知，有效值为2
                    count += 2;
                }
                break;
            case 5:
                // 对照方阵1：同理
                count += 3;
                break;
            case 6:
                // 对照方阵1：同理
                count += 4;
                break;
            case 7:
                // 对照方阵1：同理
                count += 4;
                break;
        }
        System.out.println(M + "行," + N + "列的有效值个数为：" + count);
    }

    //No.3
    //思路1：从前向后转换
    public static int StrToInt(String str) {
        char[] array = str.toCharArray();
        int len = str.length();
        int i = 0;
        //跳过开头的空白字符
        while (i < len && (Character.isSpaceChar(array[i]))) {
            i++;
        }
        if (i >= len) {
            return 0;
        }
        //跳过开头+-符号
        int flag = 1;//标记正负
        if (array[i] == '+') {
            i++;
        } else if (array[i] == '-') {
            flag = -1;
            i++;
        }
        if (i >= len) {
            return 0;
        }
        //判断并转换数字
        long ret = 0;
        while (i < len) {
            //是数字的情况
            if (Character.isDigit(array[i])) {
                ret = ret * 10 + flag * (array[i] - '0');
                if (ret > Integer.MAX_VALUE || ret < Integer.MIN_VALUE) {
                    return 0;
                }
            } else {
                //非数字直接返回
                return 0;
            }
            i++;
        }
        return (int) ret;
    }


    //思路二：从后往前转换
    //ASIC码：数字0是48，char型比int型数字大48
    public int StrToInt2(String str) {
        char[] ch = str.toCharArray();
        int len = str.length();
        if (len == 0) return 0;
        int ans = 0, m = 0;
        for (int i = len - 1; i >= 0; i--) {
            //如果非数字和符号，直接return 0
            if ((ch[i] < 48 || ch[i] > 48 + 9) && ch[i] != '+' && ch[i] != '-') return 0;
            //如果是数字，就从低位到高位累加，每次扩大10倍
            if (ch[i] >= 48 && ch[i] <= 48 + 9) ans += (ch[i] - 48) * Math.pow(10, m++);
            //System.out.println(ans);
        }
        if (ch[0] == '-') return -ans;//判断符号位
        return ans;
    }

    //拓展：[字符串相加延伸到大数相加](https://leetcode.cn/problems/add-strings/)

    //-------------------------------------------Day07-----------------------------------------------
    //No.1
    public static void main13(String[] args) {
        System.out.println(Math.round(11.5));
    }

    //No.2
    public static void main14(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        int fib_01 = 0;
        int fib_02 = 1;
        if (fib_02 == n) {
            System.out.println(0);
            return;
        }
        while (fib_02 < n) {
            int tmp = fib_01;
            fib_01 = fib_02;
            fib_02 = fib_01 + tmp;
        }
        //找到前一个比该数字小的斐波那契数
        //找到后一个比该数字大的斐波那契数
        int prev = fib_01;
        int next = fib_02;
        int minfoot = (Math.abs(n - fib_01) < Math.abs(n - fib_02) ? Math.abs(n - fib_01) : Math.abs(n - fib_02));
        System.out.println(minfoot);

    }

    //No.3
    public static boolean chkParenthesis(String A, int n) {
        // write code here
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            char ch = A.charAt(i);
            // bug在这里，一定是&&不是||
            if (ch != '(' && ch != ')') {
                return false;
            }
            if (ch == '(') {
                stack.push(ch);
            } else {
                if (stack.isEmpty()) {
                    return false;
                } else {
                    stack.pop();
                }
            }
        }
        if (stack.isEmpty()) {
            return true;
        }
        return false;
    }

    public static void main15(String[] args) {
        boolean b = chkParenthesis("()()(((())))", 12);
        System.out.println(b);
    }

    //-------------------------------------------Day08-----------------------------------------------
    // No2.
    public static void main16(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine();
        String[] array = new String[n];
        for (int i = 0; i < n; i++) {
            array[i] = scanner.nextLine();
        }

        boolean flag_len = true;
        for (int i = 0; i < n - 1; i++) {
            if (array[i].length() > array[i + 1].length()) {
                flag_len = false;
            }
        }

        boolean flag_dict = true;
        for (int i = 0; i < n - 1; i++) {
            if (array[i].compareTo(array[i + 1]) > 0) {
                flag_dict = false;
            }
        }
        if (flag_len && flag_dict) {
            System.out.println("both");
        } else if (flag_dict && !flag_len) {
            System.out.println("lexicographically");
        } else if (!flag_dict && flag_len) {
            System.out.println("lengths");
        } else {
            System.out.println("none");
        }
    }

    //No3.
    public static void main17(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int A = scanner.nextInt();
        int B = scanner.nextInt();
        int maxNum = A > B ? A : B;
        int i = 1;
        int least = maxNum;
        while (true) {
            if (least % A != 0 || least % B != 0) {
                i++;
                least = maxNum * i;
            } else {
                break;
            }
        }
        System.out.println(least);
    }


    //-------------------------------------------Day09-----------------------------------------------
    //No.1
    public static void main18(String[] args) {
        int i = 0;
        Integer j = new Integer(0);
        System.out.println(i == j);
        System.out.println(j.equals(i));
    }

    //No.2:太tm巧妙了跟之前的交换有异曲同工之妙！！！
    public int addAB(int A, int B) {
        //00000000 00000000 00000000 0000010-2
        //00000000 00000000 00000000 0000011-3

        //00000000 00000000 00000000 0000001-异或
        //00000000 00000000 00000000 0000010-按位与
        //00000000 00000000 00000000 0000100

        //00000000 00000000 00000000 0000101-5
        while (B != 0) {
            int t = A ^ B;
            B = (A & B) << 1;
            A = t;
        }
        return A;
    }


    //No.2:递归,比较难理解
    public static int foodsMethod(int n, int m) {
        if ((n == 1 && m == 2) || (n == 2 && m == 1)) {
            return 3;
        }
        if (n == 1 && m == 1) {
            return 2;
        }
        if (n == 0 || m == 0) {
            return 1;
        }
        return foodsMethod(n - 1, m) + foodsMethod(n, m - 1);
    }

    public static void main19(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int methods = foodsMethod(n, m);
        System.out.println(methods);
    }

    //-------------------------------------------Day10-----------------------------------------------
    public static void main20(String[] args) {
        //No.1
//        try {
//            int i = 100/0;
//            System.out.println(i);
//        } catch (Exception e) {
//            System.out.println(1);
//            throw new RuntimeException();
//        } finally {
//            System.out.println(2);
//        }

//No.2
//        byte b1=1,b2=2,b3,b6;
//        final byte b4 = 4,b5 = 6;
//        b6 = b4+b5;
//        b3 = b1+b2;
    }

    //No.2
    public boolean checkWon(int[][] board) {
        // write code here
        //需要判断8种情况
        int flag = -2;
        //判断横排
        for (int i = 0; i < board.length; i++) {
            int j = 0;
            for (; j < board[i].length - 1; j++) {
                if (board[i][j] != board[i][j + 1]) {
                    flag = -2;
                    break;
                }
                flag = board[i][j];
            }
            if (j == board[i].length - 2) {
                if (flag == -1) {
                    return false;
                }
                if (flag == 1) {
                    return true;
                }
            }
        }

        //判断竖排
        for (int i = 0; i < board.length; i++) {
            int j = 0;
            for (; j < board[i].length - 1; j++) {
                if (board[j][i] != board[j + 1][i]) {
                    flag = -2;
                    break;
                }
                flag = board[i][j];
            }
            if (j == board[i].length - 2) {
                if (flag == -1) {
                    return false;
                }
                if (flag == 1) {
                    return true;
                }
            }
        }

        //判断对角线[左]
        for (int i = 0; i < board.length - 1; i++) {
            if (board[i][i] != board[i + 1][i + 1]) {
                flag = -2;
                break;
            }
            flag = board[i][i];
        }
        if (flag == -1) {
            return false;
        }
        if (flag == 1) {
            return true;
        }

        //判断对角线[右]
        for (int i = 0; i < board.length - 1; i++) {
            if (board[i + 1][board.length - i - 1 - 1] != board[i][board.length - i - 1]) {
                flag = -2;
                break;
            }
            flag = board[i][board.length - i - 1];
        }
        if (flag == -1) {
            return false;
        }
        if (flag == 1) {
            return true;
        }
        return false;
    }

    //No.3
    public static boolean isLower(char ch) {
        if (ch >= 'a' && ch <= 'z') {
            return true;
        }
        return false;
    }

    public static boolean isUpper(char ch) {
        if (ch >= 'A' && ch <= 'Z') {
            return true;
        }
        return false;
    }

    public static boolean isDigit2(char ch) {
        if (ch >= '0' && ch <= '9') {
            return true;
        }
        return false;
    }

    public static boolean isSign(char ch) {
        if ((ch>=0x21 && ch<=0x2f) || (ch>=0x3A && ch<=0x40) || (ch>=0x5B && ch<=0x60) || (ch>=0x7B &&ch<=0x7E)) {
            return true;
        }
        return false;
    }

    public static void main21(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String passWord = scanner.nextLine();
        int score = 0;
        int len = passWord.length();
        if (len <= 4) {
            score += 5;
        } else if (len >= 5 && len <= 7) {
            score += 10;
        } else if (len >= 8) {
            score += 25;
        }

        int lower = 0;
        int upper = 0;
        for (int i = 0; i < passWord.length(); i++) {
            char ch = passWord.charAt(i);
            if (isLower(ch)) {
                lower++;
            }
            if (isUpper(ch)) {
                upper++;
            }
        }
        if (lower != 0 && upper != 0) {
            score += 20;
        } else if ((lower == 0 && upper != 0) || (lower != 0 && upper == 0)) {
            score += 10;
        }

        int digit = 0;
        for (int i = 0; i < passWord.length(); i++) {
            char ch = passWord.charAt(i);
            if (isDigit2(ch)) {
                digit++;
            }
        }
        if (digit == 1) {
            score += 10;
        } else if (digit > 1) {
            score += 20;
        }

        int sign = 0;
        for (int i = 0; i < passWord.length(); i++) {
            char ch = passWord.charAt(i);
            if (isSign(ch)) {
                sign++;
            }
        }
        if (sign==1) {
            score+=10;
        } else if (sign>1) {
            score+=25;
        }

        if (lower!=0 && upper!=0 && sign!=0 && digit!=0) {
            score+=5;
        } else if ((lower!=0 || upper!=0) && digit!=0 && sign!=0) {
            score+=3;
        } else if ((lower!=0 || upper!=0) && digit!=0) {
            score+=2;
        }

        if (score>=90) {
            System.out.println("VERY_SECURE");
        } else if (score>=80) {
            System.out.println("SECURE");
        } else if (score>=70) {
            System.out.println("VERY_STRONG");
        } else if (score>=60) {
            System.out.println("STRONG");
        } else if (score>=50) {
            System.out.println("AVERAGE");
        } else if (score>=25) {
            System.out.println("WEAK");
        } else if (score>=0) {
            System.out.println("VERY_WEAK");
        }

    }

    public static void main22(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String passWord = scanner.nextLine();
        int score = 0;
        //一、长度
        int len = passWord.length();
        if (len <= 4) {
            score += 5;
        } else if (len >= 5 && len <= 7) {
            score += 10;
        } else if (len >= 8) {
            score += 25;
        }

        int lower = 0;//大写字母
        int upper = 0;//小写字母
        int digit = 0;//数字
        int sign = 0; //符号


        for (int i = 0; i < passWord.length(); i++) {
            char ch = passWord.charAt(i);
            //统计小写字母个数
            if (isLower(ch)) {
                lower++;
            }
            //统计大写字母个数
            if (isUpper(ch)) {
                upper++;
            }
            //统计数字个数
            if (isDigit2(ch)) {
                digit++;
            }
            //统计符号个数
            if (isSign(ch)) {
                sign++;
            }
        }
        //二、字母
        if (lower != 0 && upper != 0) {
            score += 20;
        } else if ((lower == 0 && upper != 0) || (lower != 0 && upper == 0)) {
            score += 10;
        }
        //三、数字
        if (digit == 1) {
            score += 10;
        } else if (digit > 1) {
            score += 20;
        }
        //四、符号
        if (sign==1) {
            score+=10;
        } else if (sign>1) {
            score+=25;
        }
        //五、奖励
        if (lower!=0 && upper!=0 && sign!=0 && digit!=0) {
            score+=5;
        } else if ((lower!=0 || upper!=0) && digit!=0 && sign!=0) {
            score+=3;
        } else if ((lower!=0 || upper!=0) && digit!=0) {
            score+=2;
        }

        if (score>=90) {
            System.out.println("VERY_SECURE");
        } else if (score>=80) {
            System.out.println("SECURE");
        } else if (score>=70) {
            System.out.println("VERY_STRONG");
        } else if (score>=60) {
            System.out.println("STRONG");
        } else if (score>=50) {
            System.out.println("AVERAGE");
        } else if (score>=25) {
            System.out.println("WEAK");
        } else if (score>=0) {
            System.out.println("VERY_WEAK");
        }

    }






}
